{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #沙地治理"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sandyLandManagement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #沙地治理"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "在力扣城的沙漠分会场展示了一种沙柳树，这种沙柳树能够将沙地转化为坚实的绿地。\n",
    "展示的区域为正三角形，这片区域可以拆分为若干个子区域，每个子区域都是边长为 `1` 的小三角形，其中第 `i` 行有 `2i - 1` 个小三角形。\n",
    "\n",
    "初始情况下，区域中的所有位置都为沙地，你需要指定一些子区域种植沙柳树成为绿地，以达到转化整片区域为绿地的最终目的，规则如下：\n",
    "- 若两个子区域共用一条边，则视为相邻；\n",
    ">如下图所示，(1,1)和(2,2)相邻，(3,2)和(3,3)相邻；(2,2)和(3,3)不相邻，因为它们没有共用边。\n",
    "- 若至少有两片绿地与同一片沙地相邻，则这片沙地也会转化为绿地\n",
    "- 转化为绿地的区域会影响其相邻的沙地\n",
    "![image.png](https://pic.leetcode-cn.com/1662692397-VlvErS-image.png)\n",
    "\n",
    "现要将一片边长为 `size` 的沙地全部转化为绿地，请找到任意一种初始指定 **最少** 数量子区域种植沙柳的方案，并返回所有初始种植沙柳树的绿地坐标。\n",
    "\n",
    "**示例 1：**\n",
    ">输入：`size = 3`\n",
    ">输出：`[[1,1],[2,1],[2,3],[3,1],[3,5]]`\n",
    ">解释：如下图所示，一种方案为：\n",
    ">指定所示的 5 个子区域为绿地。\n",
    ">相邻至少两片绿地的 (2,2)，(3,2) 和 (3,4) 演变为绿地。\n",
    ">相邻两片绿地的 (3,3) 演变为绿地。\n",
    "![image.png](https://pic.leetcode-cn.com/1662692503-ncjywh-image.png){:width=500px}\n",
    "\n",
    "\n",
    "**示例 2：**\n",
    ">输入：`size = 2`\n",
    ">输出：`[[1,1],[2,1],[2,3]]`\n",
    ">解释：如下图所示：\n",
    ">指定所示的 3 个子区域为绿地。\n",
    ">相邻三片绿地的 (2,2) 演变为绿地。\n",
    "![image.png](https://pic.leetcode-cn.com/1662692507-mgFXRj-image.png){:width=276px}\n",
    "\n",
    "\n",
    "\n",
    "**提示：**\n",
    "- `1 <= size <= 1000`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [XxZZjK](https://leetcode.cn/problems/XxZZjK/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [XxZZjK](https://leetcode.cn/problems/XxZZjK/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3', '2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def gen(tp: int, num: int):\n",
    "    if num == 1:\n",
    "        yield [1, 1]\n",
    "    elif tp == 0:\n",
    "        for j in range(1, num * 2, 2):\n",
    "            yield [num, j]\n",
    "    elif tp == 1:\n",
    "        yield [num, 2]\n",
    "    elif tp == 2:\n",
    "        for j in range(3, num * 2, 2):\n",
    "            yield [num, j]\n",
    "    elif tp == 3:\n",
    "        yield [num, 1]\n",
    "\n",
    "class Solution:\n",
    "    def sandyLandManagement(self, N: int) -> List[List[int]]:\n",
    "        return list(chain.from_iterable(gen((N - num) & 3, num) for num in range(1, N + 1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "book = [\n",
    "    [],\n",
    "    [[1,1]],\n",
    "    [[1,1],[2,1],[2,3]],\n",
    "    [[1,1],[2,1],[3,1],[3,3],[3,5]],\n",
    "    [[1,1],[2,3],[3,2],[4,1],[4,3],[4,5],[4,7]]\n",
    "]\n",
    "\n",
    "class Solution:\n",
    "    def sandyLandManagement(self, size: int) -> List[List[int]]:\n",
    "        if size <= 4: return deepcopy(book[size])\n",
    "        res = self.sandyLandManagement(size - 4)\n",
    "        for i in range(size):\n",
    "            res.append([size, i * 2 + 1])\n",
    "        res.append([size - 1, 2])\n",
    "        for i in range(1, size - 2):\n",
    "            res.append([size - 2, i * 2 + 1])\n",
    "        res.append([size - 3, 1])\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "book = [\n",
    "    [],\n",
    "    [[1,1]],\n",
    "    [[1,1],[2,1],[2,3]],\n",
    "    [[1,1],[2,1],[3,1],[3,3],[3,5]],\n",
    "    [[1,1],[2,3],[3,2],[4,1],[4,3],[4,5],[4,7]]\n",
    "]\n",
    "\n",
    "class Solution:\n",
    "    def sandyLandManagement(self, size: int) -> List[List[int]]:\n",
    "        if size <= 4: return deepcopy(book[size])\n",
    "        res = self.sandyLandManagement(size - 4)\n",
    "        for i in range(size):\n",
    "            res.append([size, i * 2 + 1])\n",
    "        res.append([size - 1, 2])\n",
    "        for i in range(1, size - 2):\n",
    "            res.append([size - 2, i * 2 + 1])\n",
    "        res.append([size - 3, 1])\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sandyLandManagement(self, size: int) -> List[List[int]]:\n",
    "        if size == 1:\n",
    "            return [[1, 1]]\n",
    "        if size == 2:\n",
    "            return [[1, 1], [2, 1], [2, 3]]\n",
    "        if size == 3:\n",
    "            return [[1, 1], [2, 1], [3, 1], [3, 3], [3, 5]]\n",
    "        if size == 4:\n",
    "            return [[1, 1], [2, 1], [3, 4], [4, 1], [4, 3], [4, 5], [4, 7]]\n",
    "        result = self.sandyLandManagement(size - 4)\n",
    "        for i in range(1,size * 2, 2):\n",
    "            result.append([size, i])\n",
    "        for i in range(3, (size - 2) * 2, 2):\n",
    "            result.append([size - 2, i])\n",
    "        result.append([size-3, 1])\n",
    "        result.append([size-1, 2])\n",
    "        return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "book = [[],\n",
    "    [[1,1]],\n",
    "    [[1,1],[2,1],[2,3]],\n",
    "    [[1,1],[2,1],[3,1],[3,3],[3,5]],\n",
    "    [[1,1],[2,3],[3,2],[4,1],[4,3],[4,5],[4,7]]\n",
    "]\n",
    "\n",
    "class Solution:\n",
    "    def sandyLandManagement(self, size: int) -> List[List[int]]:\n",
    "        if size <= 4: return deepcopy(book[size])\n",
    "        res = self.sandyLandManagement(size - 4)\n",
    "        for i in range(size): res.append([size, i * 2 + 1])\n",
    "        res.append([size - 1, 2])\n",
    "        for i in range(1, size - 2): res.append([size - 2, i * 2 + 1])\n",
    "        res.append([size - 3, 1])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "book = [[],\n",
    "    [[1,1]],\n",
    "    [[1,1],[2,1],[2,3]],\n",
    "    [[1,1],[2,1],[3,1],[3,3],[3,5]],\n",
    "    [[1,1],[2,3],[3,2],[4,1],[4,3],[4,5],[4,7]]\n",
    "]\n",
    "\n",
    "class Solution:\n",
    "    def sandyLandManagement(self, size: int) -> List[List[int]]:\n",
    "        if size <= 4: return deepcopy(book[size])\n",
    "        res = self.sandyLandManagement(size - 4)\n",
    "        for i in range(size): res.append([size, i * 2 + 1])\n",
    "        res.append([size - 1, 2])\n",
    "        for i in range(1, size - 2): res.append([size - 2, i * 2 + 1])\n",
    "        res.append([size - 3, 1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "book = [[],\n",
    "    [[1,1]],\n",
    "    [[1,1],[2,1],[2,3]],\n",
    "    [[1,1],[2,1],[3,1],[3,3],[3,5]],\n",
    "    [[1,1],[2,3],[3,2],[4,1],[4,3],[4,5],[4,7]]\n",
    "]\n",
    "\n",
    "class Solution:\n",
    "    def sandyLandManagement(self, size: int) -> List[List[int]]:\n",
    "        if size <= 4: return deepcopy(book[size])\n",
    "        res = self.sandyLandManagement(size - 4)\n",
    "        for i in range(size): res.append([size, i * 2 + 1])\n",
    "        res.append([size - 1, 2])\n",
    "        for i in range(1, size - 2): res.append([size - 2, i * 2 + 1])\n",
    "        res.append([size - 3, 1])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def sandyLandManagement(self, size: int) -> List[List[int]]:\n",
    "        if size == 1:\n",
    "            return [[1, 1]]\n",
    "        if size == 2:\n",
    "            return [[1, 1], [2, 1], [2, 3]]\n",
    "        if size == 3:\n",
    "            return [[1, 1], [2, 1], [3, 1], [3, 3], [3, 5]]\n",
    "        if size == 4:\n",
    "            return [[1, 1], [2, 1], [3, 4], [4, 1], [4, 3], [4, 5], [4, 7]]\n",
    "        result = self.sandyLandManagement(size - 4)\n",
    "        for i in range(1,size * 2, 2):\n",
    "            result.append([size, i])\n",
    "        for i in range(3, (size - 2) * 2, 2):\n",
    "            result.append([size - 2, i])\n",
    "        result.append([size-3, 1])\n",
    "        result.append([size-1, 2])\n",
    "        return result\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
